package offer.day2;

import java.util.Arrays;
import java.util.HashSet;

public class No3duplicate2 {
    public static void main(String[] args) {
        int[] arr={2,3,1,0,2,5,3};
//        int res = method1(arr);
//        int res = method2(arr);
        int res = method3(arr);
        if(res==-1){
            System.out.println("数组中没有重复的元素");
        }else{
            System.out.println("数组中的第一个重复的元素为:"+res);
        }
    }

    private static int method1(int[] nums) {
        //如果要求时间优先，就使用set
        HashSet<Integer> set=new HashSet<>();
        for(int num:nums){
            if(!set.contains(num)){
                set.add(num);
            }else{
                return num;
            }
        }
        return -1;
    }

    private static int method2(int[] nums) {
        //如果要求空间优先，就使用指针+原地排序数组
        Arrays.sort(nums);
        for(int i=0;i<nums.length-1;i++){
            if(nums[i]==nums[i+1]){
                return nums[i];
            }
        }
        return -1;
    }

    private static int method3(int[] nums) {
        //时间复杂度O(n)，空间复杂度O(1)
        for(int i=0;i<nums.length;i++){
            while(i!=nums[i]){
                if(nums[i]==nums[nums[i]]){
                    return nums[i];
                }
                int temp=nums[i];
                nums[i]=nums[temp];
                nums[temp]=temp;
            }
        }
        return -1;
    }
}
